package com.azure.code.graph;


import java.util.LinkedList;
import java.util.List;

/**
 * 797. 所有可能的路径
 * 给你一个有n个节点的 有向无环图（DAG），请你找出所有从节点 0到节点 n-1的路径并输出（不要求按特定顺序）
 *
 * graph[i]是一个从节点 i 可以访问的所有节点的列表（即从节点 i 到节点graph[i][j]存在一条有向边）。
 *
 *  输入：graph = [[1,2],[3],[3],[]]
 *  输出：[[0,1,3],[0,2,3]]
 *  解释：有两条路径 0 -> 1 -> 3 和 0 -> 2 -> 3
 */
public class AllPath_797 {
    List<List<Integer>> res = new LinkedList<>();

    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        LinkedList<Integer> path =new LinkedList<>();
        traverse(graph,0,path);
        return res;
    }

    public List<List<Integer>> allPathsSourceTarget2(int[][] graph) {
        LinkedList<Integer> path =new LinkedList<>();
        path.addLast(0);
        dfs(graph,0,path);
        return res;
    }
    private void  dfs(int[][] graph,int s,LinkedList<Integer> path){
        int n = graph.length -1;
        if(s == n){
            res.add(new LinkedList<>(path));
            return;
        }
        for (int x : graph[s]) {
            path.offerLast(x);
            dfs(graph,x,path);
            path.pollLast();
        }
    }
    private void traverse(int[][] graph, int s, LinkedList<Integer> path) {
        // 添加节点s到路径中
        path.add(s);

        int n = graph.length;

        if(s==n-1){
            // 到达终点
            res.add(new LinkedList<>(path));
            path.removeLast();
            return;
        }

        // 递归每个相邻节点
        for (int v:graph[s]){
            traverse(graph,v,path);
        }
        // 从路径中移除节点s
        path.removeLast();
    }

    public static void main(String[] args) {
        int[][] graph = {{1,2},{3},{3},{}};
        List<List<Integer>> lists = new AllPath_797().allPathsSourceTarget2(graph);
        lists.forEach(System.out::println);// [0,1,3] [0,2,3]
        System.out.println("======");
        int[][] graph2 = {{4,3,1},{3,2,4},{3},{4},{}};
        List<List<Integer>> lists2 = new AllPath_797().allPathsSourceTarget(graph2);
        lists2.forEach(System.out::println); // [[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]
    }
}
